package com.zk.algorithm.binarysearch;

import com.zk.algorithm.Utils;

import java.util.Arrays;

/**
 * @author zk
 */
public class SearchMatrix2 {

    public static void main(String...args) {
        SearchMatrix2 solution = new SearchMatrix2();
        boolean searched = solution.searchMatrix(new int[][]{
                { 1,4,7,11,15 },
                {2,5,8,12,19},
                {3,6,9,16,22},
                {10,13,14,17,24},
                {18,21,23,26,30}
        }, 5);

        Utils.println(searched);
    }

    /**
     * 搜索有序二维数组
     *
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int row = matrix.length;
        int col = matrix[0].length;

        // 总共多少行
        for (int r = 0; r < row; r++) {
            // 搜索每一行
            int index = Arrays.binarySearch(matrix[r], 0, col, target);

            if (index >= 0) {
                return true;
            }

            // - (low + 1)
            col = -(index + 1);
        }

        return false;
    }

}
